\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{itemize}
\item
  若一个区间的集合为 \(\{1,1,1,4,13\}\)，则该区间最小不能被为 \(8\)\\
  \(1 = 1,2=1+1,3=1+1+1,4=4,5=4+1,6=4+1+1,7=4+1+1+1\)
\item
  \(n,m <= 100000\)，\(∑a[i] <= 10^9\)
\end{itemize}

\begin{lstlisting}
const int N = 1e5 + 5;
const int INF = 1e9;
struct Ctree
{
	int ls, rs, v;
} t[N * 40];
int rt[N], tot = 0;
void insert(int &o, int p, int l, int r, int pos, int v)
{
	o = ++tot, t[o] = t[p], t[o].v += v;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	if (pos <= mid) insert(t[o].ls, t[p].ls, l, mid, pos, v);
	else insert(t[o].rs, t[p].rs, mid + 1, r, pos, v);
}
int query(int v, int u, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr) return t[u].v - t[v].v;
	int mid = (l + r) >> 1, res = 0;
	if (ql <= mid) res += query(t[v].ls, t[u].ls, l, mid, ql, qr);
	if (qr > mid) res += query(t[v].rs, t[u].rs, mid + 1, r, ql, qr);
	return res;
}
int n , m , a[N];
signed main ()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) insert(rt[i], rt[i - 1], 1, INF, a[i], a[i]);
	cin >> m;
	while (m --)
	{
		int l , r , ans = 1;
		cin >> l >> r;
		for (;;)
		{
			int res = query(rt[l - 1], rt[r], 1, INF, 1, ans);
			if (res >= ans) ans = res + 1;
			else break;
		}
		cout << ans << '\n';
	}
	return 0;
}
\end{lstlisting}

\end{document}
